package com.hjr.leetcode.question100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *16. 最接近的三数之和
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 *
 * 返回这三个数的和。
 *
 * 假定每组输入只存在恰好一个解。
 */
public class q16 {

    public static void main(String[] args) {
        System.out.println(threeSumClosest(new int[]{1,1,1,0}, 100)); //2 -1 0 5
    }

    // 老办法 暴力迭代 475ms 42mb TODO 优化一下
    public static int threeSumClosest(int[] nums, int target) {
        //排序
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        if (ans >=  target){
            return ans;
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (Math.abs(target - ans) >= Math.abs(target - sum)){
                        ans = sum;
                    }
                }
            }
        }
        return ans;
    }
}
